package 算法.NiuKe.JZ;

import 算法.NiuKe.TreeNode;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @author:谢君臣
 * @Date:2021/4/289:47
 * @version:1.0
 * @function: 请实现两个函数，分别用来序列化和反序列化二叉树
 * <p>
 * 二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。
 * 序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），
 * 以 ！ 表示一个结点值的结束（value!）。
 * 二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
 * 例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树
 */
public class JZ62 {
    public static void main(String[] args) {
        System.out.println(Serialize(Deserialize("5,#,4,#,3,#,2")));
    }
    static String Serialize(TreeNode root) {
        String res = "";
        if (root == null)
            return "";
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        res = res + root.val+",";
        boolean flag = false;
        while (!queue.isEmpty()) {
            flag = false;//判断本是否还有下一层节点
            Queue<TreeNode> temp = new ArrayDeque<>();
            while (!queue.isEmpty()){
                TreeNode pop = queue.poll();
                if (pop.left!=null){
                    temp.add(pop.left);
                    res = res + pop.left.val+",";
                }else res = res +"#,";
                if (pop.right!=null){
                    temp.add(pop.right);
                    res = res + pop.right.val+",";
                }else res = res +"#,";
                if (pop.left!=pop.right)
                    flag = true;
            }
            if (flag)
                queue = temp;
        }
        while (res.endsWith("#,"))res = res.substring(0,res.length()-2);
        return res.substring(0,res.length()-1);
    }

    static TreeNode Deserialize(String str) {
        if (str.length()<1)
            return null;
        if (str.endsWith(",")) {
            str = str.substring(0,str.length()-1);
        }
        String[] split = str.split(",");
        TreeNode root = null;
        Queue<TreeNode> queue = new ArrayDeque<>();
        if (split.length < 1)
            return root;
        root = new TreeNode(Integer.parseInt(split[0]));
        queue.add(root);
        for (int i = 1; i < split.length; i = i+2) {
            TreeNode poll = queue.poll();
            poll.left = createNode(split[i]);
            try {
                poll.right = createNode(split[i+1]); // 可能越界
            } catch (Exception e) {
                poll.right=null;
            }
            if (poll.left!=null) queue.add(poll.left);
            if (poll.right!=null) queue.add(poll.right);
        }
        return root;
    }
    private static TreeNode createNode(String s){
        if (s.equals("#"))
            return null;
        else
            return new TreeNode(Integer.parseInt(s));
    }
}
